The present exemplary embodiments relate generally to computer vision. They find particular application in conjunction with computer vision applications, such as image classification, image clustering, image retrieval, and repeated structure finding, and will be described with particular reference thereto. However, it is to be appreciated that the present exemplary embodiments are also amenable to other like applications.
Bag-of-words approaches for computer vision applications are common place. Under such approaches, objects and scenes are modeled as large vectors of feature measurements. Typically, the features are purely appearance-based measuring, for example, local shape and texture properties. However, these features may not be very descriptive and/or discriminative. Hence, a recent trend is to use spatial relationships as features.
One approach for encoding spatial relationships is through graphs. Objects and scenes are modeled as parts (i.e., nodes), such as junctions, and relations (i.e., links) between the parts. Subgraph matching is then employed to find part instances in graph representations of image data.
Subgraph matching poses certain difficulties. Without the use of attributed graphs, subgraph matching is exponentially expensive. An attributed graph is a graph with nodes containing properties that constrain possible matches. However, noise and variability cause observed subgraphs to deviate from ideal models. This demands the use of inexact graph matching techniques, which increase matching costs and largely remove the advantages of attributed graph matching.
In view of the foregoing, it would be advantageous to have methods and/or systems that perform attributed graph matching for large collections of related subgraphs for the purpose of classifying input data in graphical form. The disclosure hereafter contemplates such methods and/or systems.